#include "main.h"

/*--- Initialize BST root ---*/
void initialize_BST(){
bst_root=NULL;
}


/*--- Insert a node ---*/
void insert_node(struct FileDescriptor* ins_val )
{

	struct SearchPath_BST *temp, *new_node, *last_node;
	/*--- create a new_node and allocate memory ---*/
	new_node=(struct SearchPath_BST*)malloc(sizeof(struct SearchPath_BST));
	new_node->data=ins_val;
	new_node->left=NULL;
	new_node->right=NULL;
	new_node->parent=NULL;

	/*--- If the tree is empty, new_node becomes the root ---*/
	if(bst_root==NULL)
	{
		bst_root=new_node;
	}
	else
	{

	temp= bst_root;
	/*--- Take the root in a 'temp' and traverse to the correct location to insert ---*/
	while(temp!=NULL)
	{

		/*--- If the node is already existing, don't insert ---*/
		if(strcoll(new_node->data->locationfullpath,temp->data->locationfullpath)==0)
		{
			printf("File path already exists\n");
			return;
		}
		else
		{
			/*--- Compare the new_node's data with existing nodes to find the correct location ---*/

			/*--- new_node < temp   =>   go to left child ---*/
			if(strcoll(new_node->data->locationfullpath,temp->data->locationfullpath)<0)
			{
				last_node=temp;		// prev node
				temp=temp->left;
			}
			/*--- new_node > temp   =>   go to right child ---*/
			else
			{
				last_node=temp;		// prev node
				temp=temp->right;
			}
		}

  	}

	/*--- save the new_node's parent, which is the last_node ---*/
	new_node->parent=last_node;

	/*--- If new_node < last_node	=>	new_node is left child of last_node ---*/
	if(strcoll(new_node->data->locationfullpath,last_node->data->locationfullpath)<0)
	{
		last_node->left=new_node;
	}
	/*--- If new_node > last_node	=>	new_node is right child of last_node ---*/
	else
	{
		last_node->right=new_node;
	}
}
}


/*--- Transplant u with v ---*/
void transplant(struct SearchPath_BST *root,struct SearchPath_BST* u,struct SearchPath_BST* v)
{
	/*--- If u's parent is NULL  =>  v will be the root ---*/
	if(u->parent==NULL)// memory leak not freeing memory
		bst_root=v;
	/*--- If u is u's parent's left child  => now u's parent's left will be v (v is taking u's position) ---*/
	else if(u==u->parent->left)
		u->parent->left=v;
	else
	/*--- If u is u's parent's right child  => now u's parent's right will be v (v is taking u's position) ---*/
		u->parent->right=v;

	if(v!=NULL)
	/*--- Now, whatever was u's parent, that becomes v's parent ---*/
		v->parent=u->parent;
}

void delete_node(struct SearchPath_BST *root, char path[locationpath_size])
{

	struct SearchPath_BST *y,*z;
	/*--- search the node whose filedescriptor->locationfullpath is the 'path'---*/
	z = search(root,path);
	/*--- If the searched node is null, that means, there is no node to delete---*/
	if(z==NULL)
	{
		return;
	}
	/*--- If z's left is null, then transplant z with z's right---*/
	if(z->left==NULL)
		transplant(root,z,z->right);
	/*--- If z's right is null, then transplant z with z's left---*/
	else if(z->right==NULL)
		transplant(root,z,z->left);
	else
	{
		/*--- If z has a right child, y = z's successor in z's right subtree---*/
		y=treeMinimum(z->right);
		/*---If y is not the direct right child of z, make y's right to be in y's position and make z's right subtree as y's right subtree so that z can be deleted---*/
		if(y->parent!=z)
		{
			transplant(root,y,y->right);
			y->right=z->right;
			y->right->parent=y;
		}
		/*---Transplant z with y and make the left subtree of z as the left subtree of its successor, y so that z can be deleted---*/
		transplant(root,z,y);
		y->left=z->left;
		y->left->parent=y;
	}
	free(z);
}



struct SearchPath_BST * getSuccessor(struct SearchPath_BST * root, struct SearchPath_BST * x)
{
	// 'x' is the node whose successor has to be found.
	struct SearchPath_BST *successor=NULL, *p;
	// if right child of x is not null, successor is the minimum in the right subtree.
	if(x->right!=NULL)
	{
		printf("Successor right != null!\n");
		successor=(struct SearchPath_BST *)treeMinimum(x->right);
	}
	// if right child of x is null, successor is the parent of some y (where y is an ancestor of x  and y is the left-child of its parent)
	else
	{
		p=x->parent;
		while(p!=NULL && x==p->right)
		{
			x=p;
			p=p->parent;

		}
		successor=p;

	}

	return successor;
}

struct SearchPath_BST* treeMinimum(struct SearchPath_BST * node)
{
	struct SearchPath_BST* temp = node;
	/*---Left most element---*/
	while(temp->left!=NULL)
	{
		temp=temp->left;
	}
	return temp;
}


struct SearchPath_BST* search(struct SearchPath_BST* node,char* search_val)
{
	struct SearchPath_BST* temp;
	//temp=(struct SearchPath_BST*) malloc (sizeof(struct SearchPath_BST));//what is the use of this code??
	//temp->data = (struct FileDescriptor*) malloc (sizeof(struct FileDescriptor));//what is the use of this code??
	temp=node;
		if(temp==NULL)
		{
			//printf("Not found!\n");
			return NULL;
		}
		while(temp!=NULL)
		{
			/*---temp's data = search_val  => found---*/
			if(strcoll(temp->data->locationfullpath,search_val)==0)
			{
				return temp;

			}
			/*---search_val < temp's data => go left---*/
			else if(strcoll(search_val,(temp->data)->locationfullpath)<0)
			{
				temp=temp->left;
			}
			/*---search_val > temp's data => go right---*/
			else if(strcoll(search_val,(temp->data)->locationfullpath)>0)
			{
				temp=temp->right;
			}


		}


}


void inorder(struct SearchPath_BST *temp)
{
	if(temp!=NULL)
	{
		/* Left - Root - Right */
		inorder(temp->left);
		puts((temp->data)->locationfullpath);
		inorder(temp->right);
	}

}




